package sortalg

import "fmt"

/**
折半插入排序
*/

type BinaryInsertSort struct {
	keyList []int
}

func NewBinaryInsertSort(sourceList []int) *BinaryInsertSort {
	bis := &BinaryInsertSort{
		keyList: sourceList,
	}

	return bis.insertSort()
}

func (bis *BinaryInsertSort) insertSort() *BinaryInsertSort {
	for i, v := range bis.keyList {
		if i == 0 {
			continue
		}

		low, high := 0, i-1
		for ; low <= high; {
			place := (low + high) / 2
			if v <= bis.keyList[place] {
				high = place - 1
			} else {
				low = place + 1
			}
		}

		for j := i - 1; j > high; j-- {
			bis.keyList[j+1] = bis.keyList[j]
		}
		bis.keyList[high+1] = v
	}

	return bis
}

func (bis *BinaryInsertSort) Print() {
	fmt.Println(bis.keyList)
}
